約 391,069 件
https://w.atwiki.jp/it_certification/pages/116.html
目的 構成 検証1 iBGP neighborの設定 検証2 eBGP neighborの設定 検証3 next-hop到達性の問題 検証4 next-hop到達性 ルーティングで対応 検証5 next-hop到達性 next-hop-self 目的 iBGP neighborの確立方法について確認します iBGPにおける、next-hop到達性の問題について確認します。 構成 設定概要 AS 1内はOSPFによってルーティングします。 R1, R2間でiBGP neighborを確立します(検証1) R2, ISP10間でeBGP neighborを確立します(検証2) 構成図 netファイル model = 3620 [localhost] [[3620]] image = C \Program Files\Dynamips\images\c3620-j1s3-mz.123-18.bin ram = 128 [[ROUTER R1]] f0/0 = R2 f0/0 [[ROUTER R2]] f1/0 = ISP10 f1/0 [[ROUTER ISP10]] 初期設定 R1 ! version 12.3 service timestamps debug datetime msec service timestamps log datetime msec no service password-encryption ! hostname R1 ! boot-start-marker boot-end-marker ! ! no aaa new-model ip subnet-zero ! ! ! ip cef ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! interface Loopback0 ip address 1.1.1.1 255.255.255.255 ! interface FastEthernet0/0 ip address 192.168.1.1 255.255.255.0 duplex auto speed auto ! router ospf 1 log-adjacency-changes network 1.1.1.1 0.0.0.0 area 0 network 192.168.1.1 0.0.0.0 area 0 ! ip http server ip classless ! ! ! ! ! ! ! ! line con 0 line aux 0 line vty 0 4 ! ! end 初期設定 R2 ! version 12.3 service timestamps debug datetime msec service timestamps log datetime msec no service password-encryption ! hostname R2 ! boot-start-marker boot-end-marker ! ! no aaa new-model ip subnet-zero ! ! ! ip cef ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! interface Loopback0 ip address 2.2.2.2 255.255.255.255 ! interface FastEthernet0/0 ip address 192.168.1.2 255.255.255.0 duplex auto speed auto ! interface FastEthernet1/0 ip address 192.168.2.2 255.255.255.0 duplex auto speed auto ! router ospf 1 log-adjacency-changes network 2.2.2.2 0.0.0.0 area 0 network 192.168.1.2 0.0.0.0 area 0 ! ip http server ip classless ! ! ! ! ! ! ! ! line con 0 line aux 0 line vty 0 4 ! ! end 初期設定 ISP10 ! version 12.3 service timestamps debug datetime msec service timestamps log datetime msec no service password-encryption ! hostname ISP10 ! boot-start-marker boot-end-marker ! ! no aaa new-model ip subnet-zero ! ! ! ip cef ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! interface Loopback0 ip address 10.10.10.10 255.255.255.255 ! interface FastEthernet1/0 ip address 192.168.2.10 255.255.255.0 duplex auto speed auto ! ip http server ip classless ! ! ! ! ! ! ! ! line con 0 line aux 0 line vty 0 4 ! ! end 検証1 iBGP neighborの設定 BGP neighborの設定 R1, R2間でiBGP neighborを確立できるよう設定します。 R1(config)#router bgp 1 R1(config-router)#neighbor 2.2.2.2 remote-as 1 R2(config)#router bgp 1 R2(config-router)#neighbor 1.1.1.1 remote-as 1 neighborの確認 上記の設定だけでは、neighborを確立する事はできません。showコマンドで確認すると、Stateはいつまで待っても、依然Activeのままです。 これは、neighborで指定したIP addressと送信元のIP addressが異なるためです。具体的に言えば、R1で指定したneighborが2.2.2.2であるのに対し、R2が送信した情報の送信元アドレスが192.168.1.2であるからです。デバッグメッセージを表示されると、neighbor確立が拒否されている様子が確認できます。 R1#show ip bgp summary BGP router identifier 1.1.1.1, local AS number 1 BGP table version is 1, main routing table version 1 Neighbor V AS MsgRcvd MsgSent TblVer InQ OutQ Up/Down State/PfxRcd 2.2.2.2 4 1 0 0 0 0 0 never Active R1# R1#debug ip bgp events BGP events debugging is on R1# *Mar 1 00 17 21.259 BGP Import timer expired. Walking from 1 to 1 *Mar 1 00 17 29.967 BGP 2.2.2.2 open active, local address 192.168.1.1 *Mar 1 00 17 30.115 BGP 2.2.2.2 open failed Connection refused by remote host update sourceの設定 neighborが確立できるよう、送信元IP addressを定義します。 R1(config)#router bgp 1 R1(config-router)#neighbor 2.2.2.2 update-source Loopback 0 R2(config)#router bgp 1 R2(config-router)#neighbor 1.1.1.1 update-source Loopback 0 neighborの再確認 neighborが確立された事を確認します。 R1#show ip bgp summary BGP router identifier 1.1.1.1, local AS number 1 BGP table version is 1, main routing table version 1 Neighbor V AS MsgRcvd MsgSent TblVer InQ OutQ Up/Down State/PfxRcd 2.2.2.2 4 1 5 5 1 0 0 00 01 57 0 R1# 検証2 eBGP neighborの設定 eBGP neighborの設定を行います R2, ISP10間で、eBGP neighborを確立します。 R2(config)#router bgp 1 R2(config-router)#neighbor 192.168.2.10 remote-as 2 ISP10(config)#router bgp 2 ISP10(config-router)#neighbor 192.168.2.2 remote-as 1 ISP10(config-router)#network 10.10.10.10 mask 255.255.255.255 ルーティングテーブルの確認 ISP10のルートである10.10.10.10はR2へ伝わっていますが、R1へは伝わっていません。 R2#show ip route Codes C - connected, S - static, R - RIP, M - mobile, B - BGP D - EIGRP, EX - EIGRP external, O - OSPF, IA - OSPF inter area N1 - OSPF NSSA external type 1, N2 - OSPF NSSA external type 2 E1 - OSPF external type 1, E2 - OSPF external type 2 i - IS-IS, su - IS-IS summary, L1 - IS-IS level-1, L2 - IS-IS level-2 ia - IS-IS inter area, * - candidate default, U - per-user static route o - ODR, P - periodic downloaded static route Gateway of last resort is not set 1.0.0.0/32 is subnetted, 1 subnets O 1.1.1.1 [110/2] via 192.168.1.1, 00 27 24, FastEthernet0/0 2.0.0.0/32 is subnetted, 1 subnets C 2.2.2.2 is directly connected, Loopback0 10.0.0.0/32 is subnetted, 1 subnets B 10.10.10.10 [20/0] via 192.168.2.10, 00 01 00 C 192.168.1.0/24 is directly connected, FastEthernet0/0 C 192.168.2.0/24 is directly connected, FastEthernet1/0 R2# R1#show ip route Codes C - connected, S - static, R - RIP, M - mobile, B - BGP D - EIGRP, EX - EIGRP external, O - OSPF, IA - OSPF inter area N1 - OSPF NSSA external type 1, N2 - OSPF NSSA external type 2 E1 - OSPF external type 1, E2 - OSPF external type 2 i - IS-IS, su - IS-IS summary, L1 - IS-IS level-1, L2 - IS-IS level-2 ia - IS-IS inter area, * - candidate default, U - per-user static route o - ODR, P - periodic downloaded static route Gateway of last resort is not set 1.0.0.0/32 is subnetted, 1 subnets C 1.1.1.1 is directly connected, Loopback0 2.0.0.0/32 is subnetted, 1 subnets O 2.2.2.2 [110/2] via 192.168.1.2, 00 27 33, FastEthernet0/0 C 192.168.1.0/24 is directly connected, FastEthernet0/0 R1# 検証3 next-hop到達性の問題 next-hopの確認 R1に10.10.10.10が伝わっていな原因を確認します。show ip bgpコマンドを見ると、ベストパスである「 」の表記がありません。また、show ip bgp 10.10.10.10を見ると、192.168.2.10 (inaccessible)と表記されています。BGPで伝わってきた10.10.10.10へのルートのnext-hop 192.168.2.10へ到達できないため、ルーティングテーブルに10.10.10.10が載らないようです。 R1#show ip bgp BGP table version is 1, local router ID is 1.1.1.1 Status codes s suppressed, d damped, h history, * valid, best, i - internal, r RIB-failure, S Stale Origin codes i - IGP, e - EGP, ? - incomplete Network Next Hop Metric LocPrf Weight Path * i10.10.10.10/32 192.168.2.10 0 100 0 2 i R1# inaccessibleの表記、next-hopである192.168.2.10へ到達できないと怒られているのが確認できます。 R1#show ip bgp 10.10.10.10 BGP routing table entry for 10.10.10.10/32, version 0 Paths (1 available, no best path) Not advertised to any peer 2 192.168.2.10 (inaccessible) from 2.2.2.2 (2.2.2.2) Origin IGP, metric 0, localpref 100, valid, internal R1# 検証4 next-hop到達性 ルーティングで対応 ルーティングの追加 検証3で確認した通り、next-hopへ到達できないのが問題のようです。そこで、next-hopへのルートをstaticに定義します。 R1(config)#ip route 192.168.2.0 255.255.255.0 192.168.1.2 ISP10(config)#ip route 192.168.1.0 255.255.255.0 192.168.2.2 ルーティングテーブルなどの確認 ISP10へのルートがR1に伝わった事を確認します。 R1#show ip route bgp 10.0.0.0/32 is subnetted, 1 subnets B 10.10.10.10 [200/0] via 192.168.2.10, 00 00 45 R1# R1# R1# R1#show ip bgp BGP table version is 2, local router ID is 1.1.1.1 Status codes s suppressed, d damped, h history, * valid, best, i - internal, r RIB-failure, S Stale Origin codes i - IGP, e - EGP, ? - incomplete Network Next Hop Metric LocPrf Weight Path * i10.10.10.10/32 192.168.2.10 0 100 0 2 i R1# R1# R1#show ip bgp 10.10.10.10 BGP routing table entry for 10.10.10.10/32, version 2 Paths (1 available, best #1, table Default-IP-Routing-Table) Not advertised to any peer 2 192.168.2.10 from 2.2.2.2 (2.2.2.2) Origin IGP, metric 0, localpref 100, valid, internal, best R1# 設定の削除 検証4で投入した設定を削除します。 R1(config)#no ip route 192.168.2.0 255.255.255.0 192.168.1.2 ISP10(config)#no ip route 192.168.1.0 255.255.255.0 192.168.2.2 検証5 next-hop到達性 next-hop-self next-hop-self 検証4のようにルーティングによってnext-hop到達性の問題を回避する事はできますが、保守しづらい設定であるだけでなくISPにルーティングの変更を依頼しなければなりません。とても現実的な対応方法とは言えません。そこで、以下のようにnext-hopを書き換える事で対応するのが一般的な方法です。 R2でnext-hopを192.168.2.10(ISP10)から2.2.2.2(R2)に書き換える設定を行います。 R2(config)#router bgp 1 R2(config-router)#neighbor 1.1.1.1 next-hop-self ルーティングテーブル等の確認 next-hopが2.2.2.2に書き変わり、BGPによる経路交換ができている事を確認します。 R1#show ip route bgp 10.0.0.0/32 is subnetted, 1 subnets B 10.10.10.10 [200/0] via 2.2.2.2, 00 00 43 R1# R1# R1# R1#show ip bgp BGP table version is 4, local router ID is 1.1.1.1 Status codes s suppressed, d damped, h history, * valid, best, i - internal, r RIB-failure, S Stale Origin codes i - IGP, e - EGP, ? - incomplete Network Next Hop Metric LocPrf Weight Path * i10.10.10.10/32 2.2.2.2 0 100 0 2 i R1# R1# R1#show ip bgp 10.10.10.10 BGP routing table entry for 10.10.10.10/32, version 4 Paths (1 available, best #1, table Default-IP-Routing-Table) Flag 0x820 Not advertised to any peer 2 2.2.2.2 (metric 2) from 2.2.2.2 (2.2.2.2) Origin IGP, metric 0, localpref 100, valid, internal, best R1#
https://w.atwiki.jp/it_certification/pages/115.html
目的 構成 検証1 Loopbackへの疎通確認 検証2 eBGPの設定 検証3 multihopの設定 目的 eBGP neighborの確立方法について確認します Loopback I/FでeBGP neighborを確立する場合は、multihopオプションが必要である事を確認します。 構成 設定概要 R1, R2は互いのLoopback I/Fに到達できるようstaticルートを設定します。 構成図 netファイル model = 3620 [localhost] [[3620]] image = C \Program Files\Dynamips\images\c3620-j1s3-mz.123-18.bin ram = 128 [[ROUTER R1]] f0/0 = R2 f0/0 [[ROUTER R2]] 初期設定 R1 ! version 12.3 service timestamps debug datetime msec service timestamps log datetime msec no service password-encryption ! hostname R1 ! boot-start-marker boot-end-marker ! ! no aaa new-model ip subnet-zero ! ! ! ip cef ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! interface Loopback0 ip address 192.168.1.1 255.255.255.0 secondary ip address 1.1.1.1 255.255.255.255 ! interface FastEthernet0/0 ip address 192.168.2.1 255.255.255.0 duplex auto speed auto ! ip http server ip classless ip route 2.2.2.2 255.255.255.255 192.168.2.2 ! ! ! ! ! ! ! ! line con 0 line aux 0 line vty 0 4 ! ! end 初期設定 R2 ! version 12.3 service timestamps debug datetime msec service timestamps log datetime msec no service password-encryption ! hostname R2 ! boot-start-marker boot-end-marker ! ! no aaa new-model ip subnet-zero ! ! ! ip cef ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! interface Loopback0 ip address 192.168.3.2 255.255.255.0 secondary ip address 2.2.2.2 255.255.255.255 ! interface FastEthernet0/0 ip address 192.168.2.2 255.255.255.0 duplex auto speed auto ! ip http server ip classless ip route 1.1.1.1 255.255.255.255 192.168.2.1 ! ! ! ! ! ! ! ! line con 0 line aux 0 line vty 0 4 ! ! end 検証1 Loopbackへの疎通確認 疎通確認 R1, R2の互いのLoopback I/Fに疎通可能かどうかを確認します。 R1#ping 2.2.2.2 Type escape sequence to abort. Sending 5, 100-byte ICMP Echos to 2.2.2.2, timeout is 2 seconds !!!!! Success rate is 100 percent (5/5), round-trip min/avg/max = 16/45/76 ms R1# R2#ping 1.1.1.1 Type escape sequence to abort. Sending 5, 100-byte ICMP Echos to 1.1.1.1, timeout is 2 seconds !!!!! Success rate is 100 percent (5/5), round-trip min/avg/max = 28/44/60 ms R2# 検証2 eBGPの設定 eBGPの設定 R1, R2間でeBGP neighborを確立します。トップページ/動作検証 ネットワーク系/20100602 BGP iBGP neighborで述べた通り、忘れずにupdate-sourceの設定を行って下さい。(恥ずかしながら、私はupdate-sourceの設定を忘れ、はまりました。) R1(config)#router bgp 1 R1(config-router)#neighbor 2.2.2.2 remote-as 2 R1(config-router)#neighbor 2.2.2.2 update-source Loopback 0 R1(config-router)#network 192.168.1.0 mask 255.255.255.0 R2(config)#router bgp 2 R2(config-router)#neighbor 1.1.1.1 remote-as 1 R2(config-router)#neighbor 1.1.1.1 update-source Loopback 0 R2(config-router)#network 192.168.3.0 mask 255.255.255.0 neighbor確立の確認 neighborの状態はIdleとなっています。上記の設定だけでは、neighborを確立できない事を確認します。 R1#show ip bgp summary BGP router identifier 1.1.1.1, local AS number 1 BGP table version is 2, main routing table version 2 1 network entries using 101 bytes of memory 1 path entries using 48 bytes of memory 1 BGP path attribute entries using 60 bytes of memory 0 BGP route-map cache entries using 0 bytes of memory 0 BGP filter-list cache entries using 0 bytes of memory BGP using 209 total bytes of memory BGP activity 1/0 prefixes, 1/0 paths, scan interval 60 secs Neighbor V AS MsgRcvd MsgSent TblVer InQ OutQ Up/Down State/PfxRcd 2.2.2.2 4 2 0 0 0 0 0 never Idle R1# 検証3 multihopの設定 multihopの設定 eBGPの場合、TTL=1のパケットが送信されます。そのためTTLを明示的に指定しないと、Loopback I/FでのeBGP neighborを確立する事はできません。 R1(config)#router bgp 1 R1(config-router)#neighbor 2.2.2.2 ebgp-multihop 5 R2(config)#router bgp 2 R2(config-router)#neighbor 1.1.1.1 ebgp-multihop 5 neighbor確立の確認 BGP neighborが確立された事を確認します。 R1#show ip bgp summary BGP router identifier 1.1.1.1, local AS number 1 BGP table version is 3, main routing table version 3 2 network entries using 202 bytes of memory 2 path entries using 96 bytes of memory 2 BGP path attribute entries using 120 bytes of memory 1 BGP AS-PATH entries using 24 bytes of memory 0 BGP route-map cache entries using 0 bytes of memory 0 BGP filter-list cache entries using 0 bytes of memory BGP using 442 total bytes of memory BGP activity 2/0 prefixes, 2/0 paths, scan interval 60 secs Neighbor V AS MsgRcvd MsgSent TblVer InQ OutQ Up/Down State/PfxRcd 2.2.2.2 4 2 6 6 3 0 0 00 01 40 1 R1# R1# R1#show ip route bgp B 192.168.3.0/24 [20/0] via 2.2.2.2, 00 01 46 R1#
https://w.atwiki.jp/kankyoanzen/pages/35.html
再帰的近代化 「再帰的近代化」ってなに?(立命館大学高橋秀寿教授) http //www5b.biglobe.ne.jp/~hidejyu/Refrexive.htm 上記ページより「現代社会の変容と課題を理解するためには非常に有効な概念。」 ウルリッヒ ベック, アンソニー ギデンズ 他著:「再帰的近代化―近現代における政治、伝統、美的原理」 http //www.amazon.co.jp/exec/obidos/ASIN/4880592366 環境問題など社会問題への対応を考える際に、近年、CSR(企業の社会的責任)や、NPO・市民活動が重視されるようになっている。また同様に、法規制だけでなく、協定や協働による自主的取り組みが重視されるようになっている。以前の公害対策等では重視されてきた、行政による規制手法が、現在は下火になってきている。 それには、社会情勢が変化し、単なる規制では有効な手段とはなりえない状況がでてきているためである。 そのような社会的な変化を説明する考え方として、。世界的な社会学者である、アンソニー・ギデンズやウルリック・ベックらによって、「再帰的近代化」という概念が提唱されている。 イギリス労働党のブレア政権も、この「再帰的近代化」の思想を受けて、新しい政策の実施を進めてきている。容器包装リサイクル法の改正においても、再帰的社会の視点をふまえた調整がなされており、今後の施策を考えていくにあたっては、欠かすことのできない視点となっている。 (1) 「再帰的近代化」の位置づけ 「再帰的近代化」とは、封建時代の伝統社会から近代社会へ進んできた中で、近代社会が様々な問題に直面し、これを克服しようとする動きの中で表れてくる変化である。現代は、いわゆる近代社会から、次のステップである「再帰的近代」へと模索をしている段階にある。これからの社会変化のあり方を示すものとも言える。 (2) 自由重視社会と福祉国家社会 これまで、「近代社会」は、自由や民主主義を追及する形で発展してきた。18世紀以前の封建社会にくらべれは、職業選択の自由、言論の自由、個人の権利などが保証され、経済も大きく発展するのに貢献してきた。 しかし一方で、個人の自由や市場が拡大した結果、新たな貧富の格差が表れたり、環境問題や社会的疎外などの市場では扱いきれない問題が深刻になってきた。このような社会問題を解決するには、自由経済に任せるのでは不十分で、政府の介入が必要だということで、先進諸国は大きな力を持つ政府による「福祉国家」を目指してきた。多額の税金を徴収する一方で、失業対策や、保険制度、各種の福祉政策などが整備されてきた。また公害などの社会的悪に対して、政府が規制を活用して対応する動きも、大きな政府の動きとして位置づけられる。 しかし、「福祉国家」を目指す動きは、政府機構の肥大化、行政システムの硬直化ももたらした。また、高福祉のシステムに対する人々の依存を強め、自立性や活力が失われてしまうことになった。さらに、これらの問題は国家財政の危機として表れてきた。欧州では、失業者への援助が、労働の必要性を低下させ、さらに失業者を増やす要因としても認識されるようになってきた。 1980年代にはいって、先進諸国は財政健全化のためにこれまでとは逆に小さな政府を指向し、行政サービスの民営化、市場化による改革を進る動きが活発化した。イギリスのサッチャー政権における民営化の動きなどがその代表例である。自由を尊重して、規制などの政府の介入をしないという方向もあわせて出てきている。 ただしこれは改革とは言っても、歴史的な流れの中で行ったり戻ったりしているに過ぎない。単に自由を重視したからといって、問題が解決するわけではなく、また同じ問題が引き起こされるだけである。 (3) リスク社会 一方で、科学技術の高度化・産業化により、化学物質、原子力、大量破壊兵器など様々なリスクへの対応が求められるようになった。これらのリスクは増大する一方であり、必ずしも国や企業など、所属する組織で対応しきれるものではなくなっている。対応しきれないリスクは、直接個人にも降り掛かり、個人の自己責任が求められるようになった。このような社会の姿は、常にリスクを背負いながら生活することを余儀なくされる点で、「リスク社会」として捉えられるようになった。 技術が多様化されることにより、一面的な規制をしていると柔軟性に欠けてしまい、効率的な技術発展が阻害されてしまうという面もある。そのため規制を撤廃する動きがある。しかし、2005年末から話題となっている建物の耐震性能偽装事件では、耐震基準の審査を民営化したために、偽装が見抜けずに、巨大な不良建築物が建ってしまう事態となっている。この偽装事件では、マンション購入者に対して補償をすることが早急に決まったが、業者の責任であるとか、場合によっては安く購入した住民にも責任があるといった主張もある。国がリスクを負えない場合には、個人にもそのリスクがふりかかってくる例である。 個人の自由も、リスクに対する自己責任とセットで渡されるようになっている。 (4) 近代化による問題を克服する「再帰的近代化」 社会学者のアンソニー・ギデンズらは、前述のような問題は、近代化が不十分であることによるという考え方に立っており、こうした従来の「近代」を「単純近代」と呼んでいる。誰もが自由を主張し、自らの問題として考えない状況では、社会問題は解決できない。 そして、近代社会が自らもたらした問題を、自ら解決していこうとする近代化のプロセスとして「再帰的近代化」を提唱している。「再帰的」とは、再び自分に向けられるという意味である。現在起っている問題について、誰か別のところに原因や対策・変革を求めるのではなく、自らと対峙して変革をしていく、もしくはそうせざるをえないことを示している。 ここに、環境問題などの社会問題をたらした原因者が、問題に直面し、問題解決に取り組むという考え方がある。 (5) 経済と環境の連関 環境問題との関連では、これまで環境と経済とは対立するものとして捉えられがちであったが、近年では「環境と経済の統合」という概念が広まりつつある。市場や経済活動そのものに、環境の価値を組み込むことで、環境調和型に変えていこうとする考え方である。 廃棄物問題に対応してEPR(拡大生産者責任)の考え方に基づいて、製造者に回収・リサイクルの実施やそのコスト負担を義務づけるなどの制度づくりが各国で進められている。一方、すべての責任・コストを製造者に負わせることは、経済効率的ではないことなどが問題とされるようにもなっている。これに対し、製造者→流通→消費者→回収・リサイクル業者→再商品化業者といった、物の流れに沿った多様な主体の間で情報交流を進めつつ各主体による取り組みを進めることで、物流を最適化するサプライチェーン・マネジメントの考え方も広まっている。このような考え方は、日本における容器包装リサイクル法改正案においても、形式的なEPRよりも、リサイクルの高度化や、企業による自主的な取り組みと報告・公表のしくみを重視するなどの形で表れている。 欧州では、大量失業者問題に対応して、企業がCSRの取り組みにおいて、雇用の創出を重視している。ホームレスなどの問題に対しても、援助よりも雇用を通じた自立を促す、社会的企業、コミュニティ・ビジネスの取り組みが広がっている。 雇用創出などは、行政が行うよりも、本業で行っている企業のほうが得意な分野である。ただし、既存の「近代化」のように自己利益のみを追求する企業であるならば、過去起こされた問題が引き起こされるだけである。企業としても、本質的に社会を考える体制が整っていないと、「再帰的近代化」による解決へは向かわない。 (6) 市民活動のありかた 市民運動も、かつては公害企業の告発や政府への要求などが中心であった。これからは、人々が環境問題の原因者としての自覚を持ち、自らの行動やライフスタイルを変えられるように促すための市民運動がより重要となると考えられる。
https://w.atwiki.jp/tk21/pages/14.html
NEXT_HOPアトリビュートのIPアドレスに到達可能(大前提) WEIGHTアトリビュートが最大の経路を優先 LOCAL_PREFERENCEアトリビュートが最大の経路を優先 ローカルルータが発生元である経路を優先 AS_PATHアトリビュートが最も短い経路を優先 ORIGINアトリビュートが最小の経路を優先 MEDアトリビュートが最小の経路を優先 IBGPピアから学習した経路よりもEBGPピアから学習した経路を優先 NEXT_HOPへ最短で到達できる経路を優先 経路がEBGPピアから学習したもののとき、学習してから最も時間が経っている経路を優先 BGPピアのルータIDが最も小さい経路を優先
https://w.atwiki.jp/it_certification/pages/112.html
目的 構成 検証1 BGPによるneighbor確立 検証2 再配送による通知 検証3 Originの変更 補足 パケットの確認 目的 BGPの基本的な設定を確認します。 構成 設定概要 BGPによってルーティングします。 構成図 netファイル model = 3620 [localhost] [[3620]] image = C \Program Files\Dynamips\images\c3620-j1s3-mz.123-18.bin ram = 128 [[ROUTER R1]] f0/0 = R2 f0/0 [[ROUTER R2]] 初期設定 R1 ! version 12.3 service timestamps debug datetime msec service timestamps log datetime msec no service password-encryption ! hostname R1 ! boot-start-marker boot-end-marker ! ! no aaa new-model ip subnet-zero ! ! ! ip cef ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! interface Loopback0 ip address 10.1.0.1 255.255.255.0 secondary ip address 10.1.1.1 255.255.255.0 secondary ip address 10.1.2.1 255.255.255.0 secondary ip address 10.1.3.1 255.255.255.0 secondary ip address 1.1.1.1 255.255.255.255 ! interface FastEthernet0/0 ip address 192.168.1.1 255.255.255.0 duplex auto speed auto ! ip http server ip classless ! ! ! ! ! ! ! ! line con 0 line aux 0 line vty 0 4 ! ! end 初期設定 R2 ! version 12.3 service timestamps debug datetime msec service timestamps log datetime msec no service password-encryption ! hostname R2 ! boot-start-marker boot-end-marker ! ! no aaa new-model ip subnet-zero ! ! ! ip cef ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! interface Loopback0 ip address 10.2.0.1 255.255.255.0 secondary ip address 10.2.1.1 255.255.255.0 secondary ip address 10.2.2.1 255.255.255.0 secondary ip address 10.2.3.1 255.255.255.0 secondary ip address 2.2.2.2 255.255.255.255 ! interface FastEthernet0/0 ip address 192.168.1.2 255.255.255.0 duplex auto speed auto ! ip http server ip classless ! ! ! ! ! ! ! ! line con 0 line aux 0 line vty 0 4 ! ! end 検証1 BGPによるneighbor確立 設定の投入 R1, R2の間で、BGP neighborを確立させます。また、互いのloopback addressをnetworkコマンドによって通知します。 R1(config)#router bgp 1 R1(config-router)#neighbor 192.168.1.2 remote-as 2 R1(config-router)#network 1.1.1.1 mask 255.255.255.255 R2(config)#router bgp 2 R2(config-router)#neighbor 192.168.1.1 remote-as 1 R2(config-router)#network 2.2.2.2 mask 255.255.255.255 設定確認 設定確認を行います。show ip protocolでは、AS番号やneighborの一覧を確認できます。 R1#show ip protocols Routing Protocol is "bgp 1" - R1のAS番号 Outgoing update filter list for all interfaces is not set Incoming update filter list for all interfaces is not set IGP synchronization is disabled Automatic route summarization is disabled Neighbor(s) - neighborの一覧 Address FiltIn FiltOut DistIn DistOut Weight RouteMap 192.168.1.2 Maximum path 1 Routing Information Sources Gateway Distance Last Update 192.168.1.2 20 00 03 08 Distance external 20 internal 200 local 200 R1# show ip bgpコマンドでは、BGPテーブルが確認できます。 R1#show ip bgp BGP table version is 3, local router ID is 1.1.1.1 - ルータID Status codes s suppressed, d damped, h history, * valid, best, i - internal, r RIB-failure, S Stale Origin codes i - IGP, e - EGP, ? - incomplete Network Next Hop Metric LocPrf Weight Path * 1.1.1.1/32 0.0.0.0 0 32768 i - " "の記載があるのが最短ルート * 2.2.2.2/32 192.168.1.2 0 0 2 i - " "の記載があるのが最短ルート R1# show ip bgp summaryはBGPテーブルの概要が確認できます。また、「State/PfxRcd」に着目するとneighborが確立できたかどうかを確認できます。neighborが確立された状態ではBGPルートの数が表示され、未確立の状態ではIdle, Active等の状態が表示されます。 R1#show ip bgp summary BGP router identifier 1.1.1.1, local AS number 1 BGP table version is 3, main routing table version 3 2 network entries using 202 bytes of memory 2 path entries using 96 bytes of memory 2 BGP path attribute entries using 120 bytes of memory 1 BGP AS-PATH entries using 24 bytes of memory 0 BGP route-map cache entries using 0 bytes of memory 0 BGP filter-list cache entries using 0 bytes of memory BGP using 442 total bytes of memory BGP activity 2/0 prefixes, 2/0 paths, scan interval 60 secs Neighbor V AS MsgRcvd MsgSent TblVer InQ OutQ Up/Down State/PfxRcd 192.168.1.2 4 2 17 17 3 0 0 00 12 02 1 R1# ルーティングテーブルには「B」の表記でルートが記載されます。 R1#show ip route bgp 2.0.0.0/32 is subnetted, 1 subnets B 2.2.2.2 [20/0] via 192.168.1.2, 00 12 50 R1# 検証2 再配送による通知 再配送の設定 R1のsecondary addressをR2に通知します。通知方法はconnectedを再配送します。 R1(config)#router bgp 1 R1(config-router)#redistribute connected BGPデータベースの確認 再配送されたルートがR2に通知された事を確認します。また、再配送によって通知されたルートのOriginが「? - imcomplete」になっている事も読み取れます。 R2#show ip route bgp 1.0.0.0/32 is subnetted, 1 subnets B 1.1.1.1 [20/0] via 192.168.1.1, 00 08 11 10.0.0.0/24 is subnetted, 8 subnets B 10.1.3.0 [20/0] via 192.168.1.1, 00 01 46 B 10.1.2.0 [20/0] via 192.168.1.1, 00 01 46 B 10.1.1.0 [20/0] via 192.168.1.1, 00 01 46 B 10.1.0.0 [20/0] via 192.168.1.1, 00 01 46 R2# R2# R2# R2#show ip bgp BGP table version is 11, local router ID is 2.2.2.2 Status codes s suppressed, d damped, h history, * valid, best, i - internal, r RIB-failure, S Stale Origin codes i - IGP, e - EGP, ? - incomplete Network Next Hop Metric LocPrf Weight Path * 1.1.1.1/32 192.168.1.1 0 0 1 i * 2.2.2.2/32 0.0.0.0 0 32768 i * 10.1.0.0/24 192.168.1.1 0 0 1 ? * 10.1.1.0/24 192.168.1.1 0 0 1 ? * 10.1.2.0/24 192.168.1.1 0 0 1 ? * 10.1.3.0/24 192.168.1.1 0 0 1 ? r 192.168.1.0 192.168.1.1 0 0 1 ? R2# 検証3 Originの変更 Originの変更 「究めるBGP」によると、検証2のように「? - imcomplete」として他ISPにルートを通知するのは望ましい状態ではありません(実践経験がないのであまりよく分かりませんが…)。そこで、route-mapを使用して、Originを「i(IGP)」に変更します。 R1(config)#route-map SET_ORIGIN_IGP permit 10 R1(config-route-map)#set origin igp R1(config-route-map)#exit R1(config)# R1(config)# R1(config)#router bgp 1 R1(config-router)#redistribute connected route-map SET_ORIGIN_IGP Originの確認 originが「i(IGP)」に変わった事が確認できます。 R2#show ip bgp BGP table version is 16, local router ID is 2.2.2.2 Status codes s suppressed, d damped, h history, * valid, best, i - internal, r RIB-failure, S Stale Origin codes i - IGP, e - EGP, ? - incomplete Network Next Hop Metric LocPrf Weight Path * 1.1.1.1/32 192.168.1.1 0 0 1 i * 2.2.2.2/32 0.0.0.0 0 32768 i * 10.1.0.0/24 192.168.1.1 0 0 1 i * 10.1.1.0/24 192.168.1.1 0 0 1 i * 10.1.2.0/24 192.168.1.1 0 0 1 i * 10.1.3.0/24 192.168.1.1 0 0 1 i r 192.168.1.0 192.168.1.1 0 0 1 i 補足 パケットの確認 debug ip bgp debug ip bgpでbgp neighbor確立の様子を確認する事ができます。 R2#debug ip bgp BGP debugging is on R2# *Mar 1 00 54 02.295 BGP Applying map to find origin for 2.2.2.2/32 *Mar 1 00 55 02.331 BGP Applying map to find origin for 2.2.2.2/32 *Mar 1 00 55 26.707 BGP 192.168.1.1 connection timed out 180236ms (last update) 180000ms (hold time) *Mar 1 00 55 26.707 BGP 192.168.1.1 went from Established to Closing *Mar 1 00 55 26.711 %BGP-5-ADJCHANGE neighbor 192.168.1.1 Down BGP Notification sent *Mar 1 00 55 26.711 %BGP-3-NOTIFICATION sent to neighbor 192.168.1.1 4/0 (hold time expired) 0 bytes *Mar 1 00 55 26.711 BGP 192.168.1.1 send message type 3, length (incl. header) 21 *Mar 1 00 55 27.711 BGP 192.168.1.1 local error close after sending NOTIFICATION *Mar 1 00 55 28.711 BGPNSF state 192.168.1.1 went from nsf_not_active to nsf_not_active *Mar 1 00 55 28.715 BGP 192.168.1.1 went from Closing to Idle *Mar 1 00 55 28.715 BGP 192.168.1.1 closing *Mar 1 00 55 48.719 BGP 192.168.1.1 went from Idle to Active *Mar 1 00 55 48.719 BGP 192.168.1.1 open active, delay 23541ms *Mar 1 00 56 02.359 BGP Applying map to find origin for 2.2.2.2/32 *Mar 1 00 56 10.539 BGP 192.168.1.1 passive open *Mar 1 00 56 10.539 BGP 192.168.1.1 went from Active to Idle *Mar 1 00 56 10.539 BGP 192.168.1.1 went from Idle to Connect *Mar 1 00 56 10.587 BGP 192.168.1.1 rcv message type 1, length (excl. header) 26 *Mar 1 00 56 10.591 BGP 192.168.1.1 rcv OPEN, version 4 *Mar 1 00 56 10.591 BGP 192.168.1.1 went from Connect to OpenSent *Mar 1 00 56 10.595 BGP 192.168.1.1 sending OPEN, version 4, my as 2 *Mar 1 00 56 10.595 BGP 192.168.1.1 rcv OPEN w/ OPTION parameter len 16 *Mar 1 00 56 10.595 BGP 192.168.1.1 rcvd OPEN w/ optional parameter type 2 (Capability) len 6 *Mar 1 00 56 10.599 BGP 192.168.1.1 OPEN has CAPABILITY code 1, length 4 *Mar 1 00 56 10.599 BGP 192.168.1.1 OPEN has MP_EXT CAP for afi/safi 1/1 *Mar 1 00 56 10.603 BGP 192.168.1.1 rcvd OPEN w/ optional parameter type 2 (Capability) len 2 *Mar 1 00 56 10.603 BGP 192.168.1.1 OPEN has CAPABILITY code 128, length 0 *Mar 1 00 56 10.607 BGP 192.168.1.1 OPEN has ROUTE-REFRESH capability(old) for all address-families *Mar 1 00 56 10.607 BGP 192.168.1.1 rcvd OPEN w/ optional parameter type 2 (Capability) len 2 *Mar 1 00 56 10.611 BGP 192.168.1.1 OPEN has CAPABILITY code 2, length 0 *Mar 1 00 56 10.611 BGP 192.168.1.1 OPEN has ROUTE-REFRESH capability(new) for all address-families *Mar 1 00 56 10.615 BGP 192.168.1.1 went from OpenSent to OpenConfirm *Mar 1 00 56 10.615 BGP 192.168.1.1 send message type 1, length (incl. header) 45 *Mar 1 00 56 10.643 BGP 192.168.1.1 went from OpenConfirm to Established *Mar 1 00 56 10.647 %BGP-5-ADJCHANGE neighbor 192.168.1.1 Up *Mar 1 00 57 02.411 BGP Applying map to find origin for 2.2.2.2/32 *Mar 1 00 58 02.463 BGP Applying map to find origin for 2.2.2.2/32 debug ip bgp updates debug ip bgp updatesで通知されたルートを確認する事ができます。 R2#debug ip bgp updates BGP updates debugging is on R2# *Mar 1 00 33 59.703 BGP(0) 192.168.1.1 rcvd UPDATE w/ attr nexthop 192.168.1.1, origin ?, metric 0, path 1 *Mar 1 00 33 59.703 BGP(0) 192.168.1.1 rcvd 10.1.0.0/24 *Mar 1 00 33 59.707 BGP(0) 192.168.1.1 rcvd 10.1.1.0/24 *Mar 1 00 33 59.711 BGP(0) 192.168.1.1 rcvd 10.1.2.0/24 *Mar 1 00 33 59.715 BGP(0) 192.168.1.1 rcvd 10.1.3.0/24 *Mar 1 00 33 59.715 BGP(0) 192.168.1.1 rcvd 192.168.1.0/24 *Mar 1 00 33 59.715 BGP(0) Revise route installing 1 of 1 route for 10.1.0.0/24 - 192.168.1.1 to main IP table *Mar 1 00 33 59.719 BGP(0) Revise route installing 1 of 1 route for 10.1.1.0/24 - 192.168.1.1 to main IP table *Mar 1 00 33 59.723 BGP(0) Revise route installing 1 of 1 route for 10.1.2.0/24 - 192.168.1.1 to main IP table *Mar 1 00 33 59.731 BGP(0) Revise route installing 1 of 1 route for 10.1.3.0/24 - 192.168.1.1 to main IP table *Mar 1 00 33 59.735 BGP(0) Revise route installing 1 of 1 route for 192.168.1.0/24 - 192.168.1.1 to main IP table *Mar 1 00 33 59.739 BGP(0) 192.168.1.1 computing updates, afi 0, neighbor version 5, table version 11, starting at 0.0.0.0 *Mar 1 00 33 59.739 BGP(0) 192.168.1.1 update run completed, afi 0, ran for 0ms, neighbor version 5, start version 11, throttled to 11 *Mar 1 00 33 59.839 BGP(0) Revise route installing 1 of 1 route for 192.168.1.0/24 - 192.168.1.1 to main IP table パケットキャプチャによる確認 BGPの様子をパケットキャプチャします。TCP 179を使用して経路を交換したりneighborを確立したりしているのが分かります。IGPと違ってTCPを使用する仕様になっているのは、信頼性が求められるからです。
https://w.atwiki.jp/satoschi/pages/621.html
東部バローチー語 |Indo-European languages|Indo-Iranian languages|Iranian languages| 言語類型 現用言語 使用文字 アラビア文字【Arab?】 type living language writing system Arabic alphabet ISO 639-3 【bgp】 言語名別称 alternate names Balochi バローチー語、バローチ語、バロチ語、バルチー語 Baloci Baluchi バルーチー語、バルーチ語 Baluci 方言名 dialect names 参考文献 references WEB ISO 639-3 Registration Authority - SIL International the LINGUIST List Ethnologue The Rosetta Project Wikipedia (Balochi language) ウィキペディア (バローチー語) Wikipedia (Balochi dialects)
https://w.atwiki.jp/mopsprogramming/pages/168.html
再帰(Recursion)というのは、言ってみれば汎用アルゴリズムの一種で、ループとか条件構造と似たようなものです。何か特定の問題をうまく解くために開発された方法というわけじゃなくて、そういうやり方を使えばコードが明快になる場合がある、という感じですか。ただ、ループや条件構造よりも、少し論理的に込み入っているので、まあ、話としてはちょっと後にでてくるわけです。で、その実現(実装)の仕方についても、ちょっと入り組んだ話があるんで、その話もちょっと触れときます。これも少し長くなりそうな気配(^^;;)。 その理屈 本質的にはループと大して変わらなくって、定型的処理を必要な回数だけ繰り返して適用するのが、再帰です。再帰定理というのがあって、再帰とループは機能的に違いがないことが証明されているそうです。つまり、原理的には再帰で書けるコードはループで書けるんだそうで、じゃあ再帰なんてなくてもいいじゃんって話なわけですが、再帰の方がソースコードの意図が明瞭で簡単になる場合もあるってのが、その存在理由とされています。っていうか、Scheme(LISP系の関数型プログラミング言語)とかだと、繰り返し適用はループじゃなくて再帰を使うんだそうです。再帰をループよりも基本的としている言語から見れば、原理的にはループは再帰で書ける、と、同じ再帰定理でも逆に読むんですね。 話によると、再帰の理屈が理解できるかどうかが、最初の躓きの石なんだそうですね、プログラミング入門では。まあ、学校で習ったことのない私にはホントにところは解りませんが、なんで「躓く」のかというと、多分、まだ定義中のものを定義の中で呼び出すからじゃないでしょうかね。以前、タイプに関連してちょっと触れたラッセルのパラドクスの出発点の話みたいな感じがするんじゃないでしょうか。不確定なものを利用していいのか、と。ホントはループと同じようにちょっと前に戻るだけなんですが、ループには普通、はじめと終わりを標す括弧構造がありますからね。再帰には普通ないです。というか、再帰は、ひとつのワード(関数)という括弧構造を途中で分断してしまいます。初めは、順番に再帰より前の部分をぐるぐる回していって、抜けたところで、今度は再帰より後ろの部分を逆順にぐるぐる巻き戻す、というイメージです。 自分自身の中で自分自身を呼び出してたら、「合わせ鏡に映る私」みたいで際限がない感じがしますよね。でも、脱出口があるんですよ、再帰には、必ず。ループだって、それを抜けるポイントつくるのを忘れたり、脱出の条件が実は絶対に成就しない条件だったりすると、無限ループに入って大変な目にあったりしますよね。同じことです。ただ、ループの場合、処理が終わったよ、ってんで繰り返しを脱出しますが、再帰の場合、脱出条件が整ったところで初めて作業が開始される場合があるという違いがあります。投網かなんかを、ビヨーンと投げて、遠くに落ちたところで、ザザザざーっと引き寄せて魚を捕る、みたいな感じですかね。投網が一番遠くに達した点が、ここでいう「再帰の脱出口」に当たります。あるいは、昔よくあった、蛇腹みたいになってて、びょーんと伸びるマジックハンドで何か取る感じ、ですか。いやあれは縮むときにはモノを放しちゃうんでだめですね。最近は、何か特殊ゴムみたいのでできてて、びょんと伸びて、先にあったものをくっつけて取るという「カメレオンの舌」みたいなのがあるようですね。 いや、まあ、こんなイメージの話ばかりしててもしょうがないですね。「脱出口」というのは、ある条件下では自分自身をもう呼び出さない、というコードです。これはぜひとも必要になります。それと、繰り返し適用されるべき処理の本体、これを記述するコードもやはり必要になります。この本体部分は自分自身の呼び出しを含んでいていいことになります、というか、普通、含んでいます。一歩手前で自分自身を適用した結果を利用するのが、再帰の特徴ですから。この処理が、脱出口に達したところから、再帰呼出し自体のあとに書かれた処理が、だだだーっと、入れ子状に適用されていって、最終的に必要な結果を得ることになるのです。 Mops/Forthでの再帰 Mops/Forthでは、自分自身を呼び出すポイントに、"RECURSE"というワードを書くことになっています。他の言語では、SchemeでもCでもそのようですが、普通は、その関数の名前で呼び出すことになっているようです。Mops/Forthでは、既定義の同じ名前のワードを呼び出して少し変更したワードでオーバーライドできるようにするため、現在定義中のワードの名前は、意図的に隠しています。その代わり、コレは再帰ですよ、ということを明示するためにRECURSEというワードを準備したわけです。 階乗計算 簡単な例で説明しましょう。階乗計算をしてみましょう。5の階乗は1×2×3×4×5ということですよ、念のため。 Factorial ( u -- u! ) dup 0 = IF drop 1 EXIT THEN dup 1- RECURSE * ; かなり限定的なものですが、簡単なところで。階乗はすぐにでかくなるので、4バイト数だと、13くらいでもう溢れちゃうでしょう。上のコードの"EXIT"というのは、もうこのワードは抜けます、というワードです。これは使わないでも同じ働きをするコードは書けて、 Factorial ( u -- u! ) dup 0 = IF drop 1 ELSE dup 1- recurse * THEN ; となりますが、生成されるマシンコードは、多分、EXITを使った方が少し小さいと思います(あやふや)。後の方が、構造は分かりやすいかもしれませんね。つまり、このワード"Factorial"脱出口は、入力値が0以下となったところです。そのときには、入力値を捨てて、代わりに1を出力します。 もっと大きい入力のときはどうするかというと、入力値を複製し、一方を1減らします。そして、その減らした方の値を入力値としてRECURSEするわけです。つまり、その定義中のワードを呼び出します。そして、その出力をもとの入力とかけ算するのです。これが階乗計算の全貌です。 数学が得意な人なら、関数式で書くと一目瞭然でしょう。Factorialは、次のような漸化式で定義されているのです。 Factorial(0) = 1 Factorial(n) = n × Factorial(n-1) (nは自然数) Forthワードの定義との対応関係も分かりますよね。もうコレで、数列とかの漸化式が与えられたら、すぐにForthで書き下せますよね .... ってことはないかな、ヤッパリ(^^;;)。 基本は、本体関数を呼び出したいところにRECURSEと書く、ということになります。上のFactorialでは、 f(n) =n*f(n-1) なので、逆ポーランド式で書けば、 (n)f = n (n-1)f * なわけで、本体関数自体は、nをスタック入力として取ることを予定していて、定義内容も、スタック上にnが一つあることを想定して書きます。スタックの状態をコメントしていくと、 f \ -- n dup \ -- n n 1- \ -- n n-1 f \ -- n (n-1)f * \ n (n-1)f * ; となるわけです。定義内で呼び出されたfをRECURSEに置き換えて、 ; f dup 1- RECURSE * ; これは、脱出条件を省いた本体の定義になってますね。 フィボナッチ数列 じゃあ、簡単なのをもう一個。他のページでも扱いましたけれども、いわゆる、フィボナッチ(Fibonacci)数列です。これは、一個前の項との比が、黄金分割比に近づいていくってことでも有名ですね。漸化式からコードを書いてみましょう。"Fibonacci"って名前のワードにでもしましょうか。定義は、 Fibonacci(0) = 0 Fibonacci(1) = 1 Fibobacci(n) = Fibonaci(n-1) + Fibonacci(n-2) -- nは2以上の自然数 でいきましょう。型通り翻訳してみます。まず、脱出条件です。 Fibonacci ( u -- u ) dup 1 = IF 0 max EXIT THEN ... まあ、間違って負の数を入力する人のためちょっと誤摩化します。0と比べて大きい方の数値をとるというのが"0 max"です。0,1なら、それぞれ適当な出力がでることが分かりますよね。ここは脱出口なので、あとはEXITです。それから、本体ですね。ウンと改行して書きましょうかねえ。 ... \ -- n 1- \ -- n-1 dup 1- \ -- n-1, n-2 RECURSE \ -- n-1, (n-2)RECURSE=Fibonacci(n-2) swap \ -- Fibonacci(n-2), n-1 RECURSE \ -- Fibonacci(n-2), (n-1)RECURSE=Fibonacci(n-1) + \ -- Fibonacci(n-2)+Fibonacci(n-1) ; おしまいです。対応関係はわかりますね。合わせて普通に書くと、 Fibonacci ( u -- u ) dup 1 = IF 0 max EXIT THEN 1- dup 1- RECURSE swap RECURSE + ; コードは短い。観念的にも明快なので翻訳も簡単。ところが、このワードは絶望的に遅いのです。その理由は計算をいっぱい無駄に重複してするからなんです。概念的に簡潔で明快だが、そのままだと効率が悪い、というのが再帰の特徴ともいえます。再帰の効率の話は後で説明することにします。フィボナッチ数列なんかは、ループで書く方がずっと速くて、コードもそんなに難しくありません。というわけでループで書いてみると、 Fibonaci2 ( u -- u ) dup 1 = IF 0 max EXIT THEN 0 1 rot 1- FOR swap over + NEXT nip ; データスタックが少しごたごたしていて、コンパイルされるマシンコードも後者の方が長い程なんですけど、無駄に再計算したりしないので、圧倒的に速くなります。まあ、気が向いたら、RECURSE版とループ版とを、入力40くらいで比べてみてください。うちの機械ではRECURSE版は一瞬壊れたのかと不安になります(^^;;)。入力値があまり大きいと、これも1セルをはみ出しちゃいますので注意。 再帰は特に数理論理学では基本的な概念です。その意味では、アルゴリズムと相性がいいんでしょうね。これは基本的に帰納関数とか再帰関数(recursive function)という話に連なるものといえるでしょうね。Recursiveが「帰納」と訳されてるんですが、どうなんですかね。論理的な意味での帰納(個々のものについて成り立つことから普遍的に成り立つことを引き出す)とは意味合いは違います。帰納はinductionですが、いわゆる数学的帰納法ってのが、mathematical inductionというんですが、これもその実体はrecursiveな証明なんですね(^^;;)。まあ、数学ではrecursionのことをinducutionともいうのだと思えばいいでしょう。 帰納関数というのは、計算可能な、つまり有限の手順で結果が出せる処理、ということで、計算可能性の理論と密接な関連があるようです。でも、コンピュータプログラミングの仕組みとしてのRecursionと特別に結びつけるのはどうなんでしょうかね。というのは、帰納関数というのは、むしろ、特殊な関数というより、計算可能なアルゴリズム全般のことなんですよ。帰納関数なら計算できる、というのは分かっている。計算可能なら帰納関数か?そうだ、と主張するのがチャーチ(Church)のテーゼですね。でも証明できない。反例もないってことは、普通の計算はみな帰納関数なんですよ。足し算も。まあ、漸化式で書けるようなものは計算できるってわかってるんだから帰納関数であるということはそうなんでしょうけど、特に再帰のときだけ関連性を云々する意味はあまりないんじゃないですかね。 ちなみに、帰納関数とはどういう関数か、っていうことの定義も帰納的(recursive ^^;;)ですね。まあ、これは、計算可能性を重視する観点(Constructivism)からは全く自然なんですけどね。計算できる関数の有限個の合成として表現できるもの、ってかんじですか。五千八百兆回の計算で実現できる、ってのが本当に現実的に計算可能かってのは、この際、気にしないんですね(^^;;)。 多分、帰納関数のrecursiveは、ある有限アルゴリスムで得た結果に、また重ねてアルゴリズムを適用していくことを有限の範囲で認める、というところに注目しての命名と推測されます(多分、定義の仕方がrecursiveだからではないと思います)。コンピュータのRecurseも「重ねて適用する」というか「再施」という感じが共通ですけどね。要は一種の関数の合成なわけですが。気分は同じなんですかね。 再帰と効率 再帰はそのままやると、効率がよくありません。メモリー消費もバカにならない、といわれることもあります。どういうことなのでしょうか。 再帰は、ストレートに実装すると、現在定義中の関数(ワード)をそこで呼び出すという形式になります。問題は、その関数の呼び出しのときにどういうことが普通おこなわれているのかです。大抵の場合、入れ子になった呼び出しのときは、その呼び出しの都度、スタックに値を積んでいくようになっているのです。Forth系でいうと、いわゆるリターンスタックです。つまり、戻る地点のアドレスをメモリーに保存しておくんですね。それと、C言語系だと、帰るときにもとに戻しておかないといけないレジスタも保存します。さらに、局所変数もいっぱい使いますが、外に出て帰ってきたときに(呼び出しがリターンしてきたとき)局所変数の値が分からなくなっては困るので、呼び出しのときは、それらも保存します。関数への引数の現在値も呼出し前に保存しておかなければなりません。あれやこれや、C言語系では結構呼び出しには保存すべきものが多いんですね(値の状態をまとめて、"コンテクスト"とかいうようです。)。C言語系では各関数がスタックフレームと呼ばれるメモリー枠を確保して、そこに保存します。各関数は大抵自分専用のスタックフレームを確保します。そのフレームを関数呼出しの度毎に、まさにスタックのように積んでいくんですね。そのような各関数毎のスタックフレームはかなり大きくなる傾向にあります。それに入れ子の呼出しが嵩めば、スタックフレームはどんどん積もっていきます。例えば、ひとつの関数が20セル分(現実と比べるとかなり小さめではないかと思いますが)のスタックフレームを確保したとして、100回再帰すれば、総計2000セル分のスタックフレームが必要になるわけです。これに対して、ループは、ひとつの関数内で、実行箇所をちょっと前に戻すだけで済みます。いちいち、戻る毎にスタックを準備する必要がない。これが、「再帰はスタック(メモリ)を消費する」といわれていることの中身です。 まあ、メモリーが希少だった頃はメモリー効率の意味は大きかったんでしょうが、今では、アプリケーションレベルの話としてはそれほどともいえません(埋め込みとかだと、まだ問題になる)。ところが、再帰は、計算速度も遅くなるのです。というのは、再帰の度毎にメモリーに沢山の値を保存するわけです。以前の回で触れましたが、メモリーへのアクセスというのは、CPU内部での計算と比べて概して遅いわけです。呼び出しから戻るときには、レジスタを原状回復して戻すわけで、一旦保存された値は、この度はまた読み出されなければなりません。10アイテム分で10回の回帰だと、行きに100アイテム分の保存、帰りにまた100アイテム分の読み出し。たった10アイテムで10回の呼出しなのに、それだけのために200回という大量のメモリーアクセスをおこなうことになるわけです。 しかし、本当は、これは特に再帰だけの問題ではありません。関数(サブルーチン)の呼び出しそのものが、結構負担が大きいものなのです。再帰は、それをたくさんすることになる、というに過ぎません。この超過負担のため、C言語などでは、関数をできるだけ大きくして、他の関数の呼び出しを最小限に抑える方が、少なくとも実行速度の点では有利になっているのです。ただ、あまりにも長い関数を定義すると、何をやっているのか辿るのが大変になります。つまり、コードの保守性が落ちるというわけです。モジュラーなコードも書けなくなります。コンパイラがうまくやってくれることが多くなったそうですが、それでも、この実行速度と保守可能性のせめぎ合いは、速さが必要なコードでは、今でも大きな問題らしいです。 ここまで、C言語、C言語と言ってきたことにもお気づきでしょう。ここで言っている超過負担の問題は、よく考えてみると、関数、もっと広義の呼び名ではサブルーチンの呼び出しのときの仕組みがそうなっているからでてくるものだということに気付くでしょう。C言語では、標準的に、上のようなスタックフレームを作って、関数呼び出し時にたくさんのアイテムをそこに保存するという仕組みが採用されています。多くのコンピュータもそのような使い方をすることを前提につくられています。でも、そうしなきゃいけないってものではありません。別のやり方もありうるのです。ですが、そうはいっても、局所変数を使わない言語というのは、現在ではほとんどありません。呼び出しの前後で維持しておきたい局所変数は、その関数専用のスタックフレームを作ってどこかスレームに保存しておき、用がなくなったらフーレムメモリー領域ごと解放する、というのが一番効率がいいのです。そんなこんなで、スタックフレームを積む、というのが標準的なサブルーチンコールの方式なわけです(歴史的には逆かもしれませんが)。また、計算処理には遅いメモリーよりも、レジスタで計算したいため、レジスタの個数がいきおい増えてきています。いわゆるRISCと呼ばれるタイプのCPU(PowerPCもそれに含まれる)では、レジスタの個数はかなり多くなっています。値をメモリーにあるまま操作することはできず、必ずいったんレジスタに読み出すことになっているからです。サブルーチン呼び出しの前後で値を変えてはいけないレジスタというのも相当個数に上ります。かつてのMacで使われたPowerPCのCPUだと、大体、整数用と小数用、それぞれ20本ずつくらいが、値を変えてはいけないレジスタです。つまり、それらを使う場合には、いったんその値をメモリーに保存して、使った後は元に戻して返してやる必要があります。ちなみに、PPC Macintoshでは、これらのレジスタは局所変数のために使うとされています。レジスタでおさまりきれない局所変数は、メモリーを直接使います。結局、サブルーチン呼出しのときに必要になるメモリーアクセスの主要部分は、局所変数を使うために必要となる保存/回復操作であるということになります。 それなら、局所変数を使わないなら負担は軽くなるのか。実際その通りなのです。局所変数を使わない言語、といえば、もちろん、Forth系はまさにそうです。確かに、コードの行き先の方向転換をするだけでも、一本調子で実行が先に進むのと比べると平均的にはいくらかのロスはあります。それはループも同じことで、その点を更に最適化しようという話もあります。ですがその話は別とすると、Forth系は呼び出しの超過負担が非常に小さいことが特徴となっています。Mopsの場合も、局所変数を使えば使った分だけレジスタの保存/回復作業を必要としますが、それなしでやれば、呼び出されるワードへの入力のためのデータスタックと、戻るところを記録しておくリターンスタックアイテム一個分(ただし、2セル(64ビット)になっている)だけしか、メモリーとの遣り取りはありません。重複して保存されるアイテムというのもなく、必要最小限となっています。ですから、Mopsでは再帰の非効率がこの局面で問題になることはないと考えて良いと思います。ただ、このように、Mopsではもともと再帰があまり非効率的ではないせいか、あまり頑張って最適化しようとはしていません。後に述べるようなTail-Recurse最適化もないようです。いずれにせよ、その言語のサブルーチン呼び出しの仕組みが大きくかかわっているのです。Mopsは再帰それ自体は遅いわけではない言語ということになります。 再帰呼び出しの最適化 レジスターや、その他アイテムを保存-回復するための超過負担を軽減する簡単な最適化方法があります。LISPやSchemeなど、再帰を繰り返し適用の基本としている言語では、このような最適化は仕様として要請されてさえいるようです。いわゆる、末尾再帰最適化(tail-recursiton optimization)です。(訂正:LISPは末尾再帰最適化を仕様として要求するわけではないようです。言語仕様を見たわけではないので、あやふやですみません。Schemeでは仕様のようです。いずれにせよ、関数型言語は、再帰を繰り返し適用の基本形としているのは間違いないようです。ループの機構が無いわけではないらしいですが。) 実際には、これは再帰の最適化というより、サブルーチン呼び出し一般の最適化方法で、もっと広い意味では、tail-call optimizationと呼ばれています。末尾呼出し最適化、ですかね。 ただ、この最適化方法は、特定の局面でしか利用できません。その名が示す通り、[再帰]呼出しが、呼出しがわの末尾にある場合に限ってできるやり方なのです。末尾にある、とはつまり、呼出しがわの実体処理はもう終わっているので、呼び出した処理が終わって自分に処理が戻ってきた後は何もすることが残っていないという状態です。この状態で再帰呼出しをするように注意すれば、最適化が適用できて超過負担を軽減することができる、というわけです。 具体的には、まず、呼出し側には処理が残っていないのですから、そこで使われる局所変数は、もう呼出し前に保存しておく必要がありません。さらに、再帰で10段階呼び出しているとして、10番目が終わったら9番目に戻るわけですが、9番目に残っている処理は、8番目に戻る、ということだけです。なので、もう10番目から全部すっ飛ばして、一番最初に一気に戻ってしまえるわけです。で、一番最初(再帰を含んでいる関数)が呼び出されたときの状態を回復して振り出しに戻してやれば完璧です。で、再帰としてこの状況をもう一度考えると、保存するものもない、よって回復するものもない、自分自身の呼出しなんだから、出かけるのも自分自身の頭、戻ってくるところも自分自身のお尻と決まっているわけで、いちいち、お出かけの形を取る必要はないわけです。つまり、もともと、再帰するのにリターンアドレスの保存さえ不要なわけです。スタックフレームなどつくらず、普通に実行を頭に戻すだけのコードで書けるのです。再帰をこのような実行コードとしてコンパイル(ないし解釈)することを末尾再帰最適化というわけです。このようなことができるなら、再帰呼出しの特有の超過負担はほとんどなくなってしまうわけです。 用語法補遺:ちょっと、言葉の使い方について補足します。上で、末尾再帰最適化のことを大雑把に説明しました。再帰を用いているコードが末尾再帰になっているかどうかは型通りのチェックでわかりますし、型通りに単純な分岐ループ(頭に戻るGotoみたいなもの)に変形できるわけで、多くのコンパイラはこの最適化を自動的に行うようです。特に上にも書きましたがSchemeでは言語仕様として最適化が要求されていると聞いたことがあります。そのせいか、最適化されている末尾再帰という意味で、単に「末尾再帰」という言い方もときどき見かけます。なので、「末尾再帰」と聞いたら、言葉通り末尾で再帰をしているコードだという意味で言っているのか、最適化された再帰(つまり、効率が悪くない再帰)コードという意味で言っているのか、用心する必要があるようです。 Fibonacciはなぜ遅かったのか Mopsは再帰の超過負担が小さい、といいました。なのに、"Fibonacci"は、なぜ絶望的に遅かったのか。これは呼出し云々というより、再帰そのものの実装の問題なのです。前にもいいましたが、そのままでは無駄な計算が多すぎるのです。再帰の観念そのものには問題はないと私は思います。実現手順の問題です。いってみれば、その直前までに得た情報のほぼ半分を捨ててしまって、はじめから再計算しているのです。例えば、Fibonacci(5)を得るために、Fibonacci(4)とFibonacci(3)を得て、それを足し合わせたとします。じゃあ、次にFibonacci(6)に移ろうとしたときには、今得られたFibonacci(5)に、前にもう計算してあったFibonacci(4)を足せばいいわけじゃないですか。少なくとも、再帰関数の概念ではそういうものだと私は思います。ところが、上の二重のRECURSEを使ったコードでは、Fibonacci(5)は使いますが、Fibonacci(4)は0からまた再計算しているのです。七項目を得るときには、五項目は0から再計算、八項目を得るときには、六項目は再計算、、、という具合で、しかも各再計算の中身も、そこまで上がってくるまでに再計算のオンパレードです。それで、項目40ともなると、もうものすごい計算量なのです。ぼんやり考えると、計算の規模は2nよりちょっと小さいくらいですかね。計算自体がフィボナッチ数列みたいに増えていくんで、もしかして黄金分割比(1.6ちょっと)のn乗規模なんでしょうか --- 計算方法知らない(追加:おまけ付けました)。小さいnだと計算自体がフィボナッチ数列+1で増えていく感じなんで、40項目を計算するには初めの項のだいたい二億倍以上の時間がかかる感じです(^^;;)。 だいたいのイメージですが、関数"fibo(n)"と短くして-- そうしないと字がかぶっちゃう(^^;;) -- 、fibo(6)でどれくらい計算するかを図に書いてみました。二つの矢印が交わるところでひとつ足し算です。これを全部するんですよ。そいでもって、fibo(7)に上がるときは、左側のfibo(5)を頂点とした一房の部分を右側にもう一個くっつけて、それと、fibo(6)と足してfibo(7)です。かなり計算がダブってることが分かると思います。でかい絵ですみません(でも、結構、描くの大変だったんですよ、ええ。)。 比較のために、ループで計算するときの手順は次のような感じです。 上の足し算12個に対して、こっちは5個です。fibo(7)を計算するには、上ではあと8回足し算が増えますが、こっちはあと1個増えるだけです。 ここは、おまけ そんなわけで、再帰自体が悪いわけではない、ってことで再帰の再起を賭けて、再帰を使った速いフィボナッチを書いてみました。 Fib-Recurse ( u1 u2 #itm -- res ) dup R 0= IF nip R drop EXIT THEN swap over + R 1- RECURSE ; Fibonacci3 ( #itm -- res ) dup 0 = IF 0 max EXIT THEN 0 1 rot Fib-Recurse ; って、よーく見ると分かっちゃうんですが、実はこれは再帰のふりして実体はループなんですね。ループのコードのループ部分を再帰で書いただけなんですよ、実は。それでも、"Fib-Recurse"はまぎれもなく再帰を使ったコードですよねえ。こうするだけで速いんですよ。再帰は使い方を工夫しろ、ということでしょうね。 フィボナッチついでに、もっと大きい数も出せるやつを書いておきましょう。Mopsにはdoubleというライブラリファイルがついています。これは、小数の方じゃなくて、2セル整数を扱うためのライブラリです。これをつかって、64ビット数まで結果をだせるFibonacciを定義してみます。ループの方を使いますね。 まずPowerMops上で、 // double enter として、doubleファイルをロードしてください。それから、ワードを定義しますが、名前は、まあ、"Fibonaccid"とでもしときます。 Fibonaccid ( u -- ud ) dup 0 = IF 0 max s d EXIT THEN R 0 s d 1 s d R FOR 2swap 2over d+ NEXT 2swap 2drop ; これで、93項までは大丈夫です。計算は一瞬です。ただ、残される結果がダブル形式でよくわからないかもしれないので、終わった後に、 ud. enter としてみてください。負号なし64ビットだと完全に使い切れる桁は10進では19桁分だけですね。1.8446×1019程度を超えると溢れます。Schemeとかみたいに64ビット数を超える巨大数値計算のサポートは、いまのところないです(おそらく)。自分でライブラリを書く必要があります(多分)。 上で、再帰による遅くないFibonacci数列のコードを書きましたが、この中で再帰を含んでいるワード"Fib-Recurse"は奇しくも(?)末尾再帰になっています。PowerMopsでは別段これを分岐としてコンパイルするような最適化は働きませんが、それでも、十分速いものになっています。末尾再帰というのは要するに、再帰した結果に何らかの処理を加える必要がないような書き方をするということです。再帰を基本とするプログラミング言語では、できるだけ末尾再帰に持ち込めるように書け、といわれます。でも、それって、結局、ループで書くってことなんじゃないかという気がします。再帰のイメージとしては、まず初期条件が与えられていて、そこに至るまで準備していって、到達した地点からパタパタと計算して最終結果を得る、という感じだったんですが、末尾再帰というのは、抜けたときには全部終わってるんで、結局、初めから計算してるんですね。それは、ループのイメージに近い気がするわけです。ま、上のコードは、まさにループのコードを翻訳したんですけどね(^^;;)。 ストレートに再帰を適用した場合、具体的計算を留保しつつも第n項めから始めていって、端に至って最終的計算を開始する、という感じなんですが、上のようなコードの場合、実はいきなり初めの項から計算を始めてる。そして、再帰呼出しした自分自身にパラメターとして与えているのは、実は、残り項数なんですね。それ、まったくループのインデックスじゃないですか。ループのインデックスの値が破壊的に変更されるのがよくない、とか関数型言語ではいうわけで、それが再帰を好む一因となっているわけですが、う~んというかんじですねえ。関数への入力だから、その都度違っていいのか、そういうことか?ええっ?詭弁(イイノガレ)じゃねえのか?(^^;;)なら、MopsのFOR-NEXTループ版だって、ループのインデックスは使ってないぞ(使えるけど^^;;)。何か別のやり方もあるんでしょうかねえ。まあ、よくわかりません。 前へ 次へ 目次へ トップページへ
https://w.atwiki.jp/ajisaibox/pages/16.html
概要 科学技術が進んだ世界のはなし。ヒューマノイドと人間たちの近未来SF。 あらすじ 時系列は以下同順。 Blue-Gene Project 鏡屋と名乗る者から招待を受けた者たちは地下に閉じ込められ、殺し合うことを命じられる──。 誰から死ぬのかまったくわからないサバイバル殺人ゲームと、追い詰められた人々の狂気のはなし。 この世界に名前をください 記憶を持たない住人全員が、屋敷から出ることはできないと、誰から教えられたわけでもなく知っていた。 お互いの素性も、自分の正体も知らない人たちが、閉鎖された世界で生きるはなし。 Terrestrial とあるヒューマノイドが引き起こしたハッキングによる大規模ネットワーク災害、通称「666事件」。 その原因となるAH-666MM個体、八戸見ユーマをめぐって繰り広げられる、アンドロイドと人間たちのはなし。 本編 未執筆 ▼最新話 短編「 枯れない若葉 」 一人ぼっちの女性と人間になりたかったヒューマノイドのはなし
https://w.atwiki.jp/imops-forth/pages/25.html
概念的説明 † 再帰関数をご存知なら、この区画は飛ばしてかまいません。 再帰関数(リカーシブ ファンクション)は計算理論に用いられて、計算機科学でもよく取り上げられるようだ。 このリカーシブ recursiveの日本語訳としては"帰納"もある。数学的帰納法の帰納であるが、これは論理的な推論としての帰納(induction)ではないので混乱する。高校数学で出会う"漸化式"もリカーシブ リレーションである。 名詞の"再帰"は電算系ではrecursion、動詞の"再帰する"はrecurであり、forthのワードrecurseは英単語ではないようである。 これは要するに数列である。数列は、順番を表す整数ないし自然数を定義域とした、ステップ番号値の関数として考えられるわけだが、その場合に、数列の各値が、当の数列の前のステップの値(複数もあり得る)との数式的関係によって定まるものが、再帰関数である。そこに初期値を与えると、その数式的関係に従って一挙に数列全体が決まり、関数が定義されるというわけである。 数列やステップ関数が出てくるのは、ひとつには漸化式、また数学的帰納法の関連、そして解析学の数列(級数)がある。これらは番号付き系列という意味で形式的には似ているが、着目点がだいぶ異なる。解析学(微分積分)では数列や級数が収束するかどうかが非常に重要な要素である。他方、漸化式では、再帰的な関係を解いてステップ値nだけの関数に還元してしまうことが主な問題であり、数学的帰納法では初期値を与えれば全体が決まる関係を示すというところが重要である。 計算機的に見れば、漸化式タイプのものが対象ということになるだろう。漸化式を人が解くには、nだけの式に還元しないと手間がかかってしょうがないが、計算機は計算がメチャクチャ速い一方、工夫して解く能力は無いので、ベタで計算してしまおうという話になる。これを実現するのが再帰である。 Forthの再帰 (RECURSE) 多くのプログラミング言語では、現在定義中の関数を、その定義内で呼び出すことを認めている。 これに対して、forthでは、現在定義中のワードの中から、当のワードを呼び出すことは禁止されている。他方で再帰的な関数定義を実現するためRECURSEというワードが定義されている。当の関数を呼び出したい場所に、RECURSEと書くのである。これは、同じ名前のワードを再定義するとき、既存の同名のワードを呼び出し可能にしておけば変更部分だけを追加するだけで済むので便利だから、という判断である。定義中のワードが呼び出せてしまったら、同名の新しい定義の中から古い定義には接近できなくなってしまうので、名前を変えるなど操作しないといけなくなるからである。 以下、簡単なforthのコードは読めるということを前提として、比較的単純な再帰的定義の例を解説し、関数呼び出しが可能な場合との比較を行う。続いて、数学風の漸化式から始めて、それをforthの再帰に解体する方法を示す。さらに、計算機に対する負担が極めて重い再帰を回避して、漸化式をforthのループ計算に落とす方法について述べる。 フィボナッチ数列 フィボナッチ数列は、手前二つの項の和が次の項になるという関係の数列で、初期値は、0ベースにすれば、0,1である。 数列の第n項をで表せば、 という関係になる。 これを実現するforthワードfibの定義は、次の通りである: fib ( n -- n ) dup 1 if 1- dup RECURSE swap 1- RECURSE + then ; 短い。そして、一見、暗号にしか見えず、recurseがcurseに思えてくる(苦笑)。 まず、最後の then は、if文の"括弧閉じ"であって、"条件が成り立つとき"という意味ではないというのはforthの基本である。混乱するという理由で、end-ifに改名して使っている人も多い。 このif括弧は脱出条件を定めている。入力が0のときは0、1のときは1を返すだけで抜けてしまう。それより大きい入力のときだけ中身を実行するのである。再帰的定義には、脱出条件が不可欠であって、これが無いと、理論上は永久に計算が止まらず、実際上はスタックオバーフローでアプリケーションがクラッシュするまで続行される。 なお、ifは判定値をひとつスタックから消費する。 脱出条件を取り除いた内容面を考察する。 1- dup RECURSE swap 1- RECURSE + まず、RECURSEは要するに、fibを呼び出すということである。なので、fibと書き換えてみる: 1- dup fib swap 1- fib + 入力をnとしてときのスタックの状態を追ってみよう。 n \ 入力 1- \ -- (n-1) dup fib \ -- (n-1) [(n-1)fib]=fib(n-1) swap \ -- fib(n-1) (n-1) 1- \ -- fib(n-1) (n-2) fib \ -- fib(n-1) [(n-2)fib]=fib(n-2) + \ -- fib(n-1)+fib(n-2) と、このように紛れもないフィボナッチ数列の定義である。 ポイントは、ワードfibが1入力1出力のワードであるので、RECURSEのところでトップスタックの入力値一個と結合して、それにfibを適用した出力値に入れ替わる、と考えるところである。後は、スタック操作を工夫するくらいである。 ところで、実はforthでも定義中のワードを定義内で呼び出せるようにもできる。というのも、定義中は名前を検索から隠しているに過ぎないからである。それを露にするだけで呼び出しは可能となる。それをするのがRECURSIVE宣言である。Forth標準ではないが、gforthにあるようだ。iMopsにも定義してある。定義が始まってから、初めにRECURSIVEと書けば、そのワード限りで、定義内からそれ自身を呼び出すことができる。フィボナッチ数列なら、次のようになる。 fib ( n -- n ) RECURSIVE dup 1 if 1- dup fib swap 1- fib + then ; しかし、あまり分り易くなったとはいえない。forthのように入力をスタックから取る場合は関数の適用は見えにくい。むしろRECURSEと書いた方が再帰に気づき易いように思う。 他方、変数を用いて、パラメターを明示的に書く言語では、定義中の関数と同じ名前で関数呼び出すことで、見やすくなるであろう。しかし、基本的には、言語に関係なく、やることは同じである。まず、脱出条件を、対応する値を返すように書いて、内容は、再帰呼び出しによる計算の結果値をリターンすれば良いわけである。 漸化式のforth-recurse化 まず、漸化式を適当に書いて、それをforthのRECURSEで実装してみる。 ここでは、次の式にしてみる。特に意味はなく、適当に決めた。 n-3の項まで関連するので、初期値は3つ必要である。0から始めて順に0,1,2、とでもしておこう。 ワード名はseq1としておこう。まず、脱出条件を書く。 seq1 ( n -- n ) dup 0 = if drop 0 EXIT then dup 1 = over 2 = or ?EXIT (途中) 入力が0以下のときは、入力を落として0を返して抜ける。EXITというのはこのワードの処理を抜けるワードである。Forthではif-thenの入れ子はコードを読みにくくするとされ、EXITを比較的愛用する。 入力が1か2のときには、そのまま抜ける。overは、ひとつ飛んだ下の値をコピーしてトップに置くワードである。等号条件判定の真偽値を飛び越えて、入力値をコピーするのである。?EXITは、"if EXIT then"の短縮形である。Forth標準規格ではないので定義されていない環境もあるかも知れない。いちいちdupしているのは、条件判定後にも入力値を残すためである。ifも?EXITも、比較演算の結果をひとつ、条件成就のいかんに関わらず消費するので、このプロセスを過ぎた後は、必ず入力値がひとつ、スタックに残っている。 さて、本体にうつろう。 定義式をf(n)=という形に書き換える。単純な移項である。 この右辺を実現すれば良い。 右辺は、f(n)を三個含むので、RECURSEも三個必要である。スタック上の掛け算、足し算、引き算をなるべく線形にできるように順序を考えると、まずn-2にfを適用し、次にn-3にfを適用して3倍して、前の値から引いてから2倍、最後にn-1にfを適用して足す、というのが簡単そうである。かくして本体は、 dup 2 - RECURSE over 3 - RECURSE 3 * - 2* swap 1- RECURSE + となる。意外に簡単! 使用するスタック上の値をいつも上2つぐらいに止めておくと作業が楽である。3つは苦しくなる。4つは厳しい。だいたいforthの標準ワード内で作業しようとすると、そのような感じになる。多過ぎるときは、リターンスタックや局所変数に一時退避させて調整する。 かくして、まとめて定義すれば、 seq1 ( n -- n ) dup 0 = if drop 0 exit then dup 1 = over 2 = or ?exit dup 2 - recurse over 3 - recurse 3 * - 2* swap 1- recurse + ; となる。 このワードは3つも再帰しているので、計算機への負担は、入力が大きくなると爆発的に増加する。seq1を試す場合は、入力は30程度までに止めておいた方が無難である(インタープリタが固まってしまう)。 ループへの翻訳 再帰関数は計算効率が悪い。これは、関数の呼び出しが嵩み、スタックフレームが大量に消費されることとか、呼び出しの際のパラメターのsave/restoreのせいでメモリーアクセスが増えること、呼び出しそのものが時間のかかる処理であること、などのような、こともある。しかし、実はそれだけではない。再帰は、後でも述べるが、本当はしなくても良い計算を無駄に何回も繰り返しているのである。そこで、無駄に計算をしない、単純な繰り返しループに書き換えるという考えが出てくる。効率化方法としてよくいわれるテイル・リカースとかテイル・コール最適化という方法は、最後にある呼び出しはリターン手続を省略できるという話のようであり、無駄な計算そのものを減らすという話ではないようである。 問題状況を分解してみよう。 例えば、フィボナッチ数列の場合、再帰は、まず、fib(n-1)を0から計算する。さて次は...?、となって、fib(n-2)といわれると「え〜〜?またかよ!」とばかりに、またfib(n-2)を0から計算し始めるのである。そして、両方が出来上がったところで、改めて足し算をしてfib(n)の値として返す。しかし、fib(n-1)を計算した途中にfib(n-2)は手に入れたはずである。fib(n-2)が分っているなら、fib(n-1)に足すだけで、一回でfib(n)が得られるはずなのだが、コンピュータはfib(n-1)を得た時点で、それ以前のことをキレイサッパリ忘れてしまうのである。おバカにもほどがある! 本当は上の書き方は控えめである。もっと多くの無駄な計算が実施されている。 というのは、上のような0からのやり直しは、各段階で起こっているのである。つまり、f(3)からf(4)を求めるのに、f(2)を0から求め、f(3)に足す; f(4)からf(5)を求めるのに、f(3)をもう一回0から計算してf(4)に足す;f(5)からf(6)を求めるのに、f(4)をもう一回0から計算してf(5)に足す、 というのである。 そして、「もう一回0から計算して」というのが、そのような各段階がまさに同じように繰り返されるということを意味しているのである! 足し算の計算回数はになるようである(但し、n=0のときは0回)。効率は規模ということになる(細かくいうとくらい?)。 このように考えてみると、計算結果を記憶しておくことが、再帰を回避して、結果にリニアーに到達するための鍵になるのではないかと思われてくる。もしも、再帰関数が、2つ手前までの値に関連するなら、それら2つの結果を保存しておけば足りるであろう。 一般に、漸化式でf(n)が依存するf(n-x)と同じ個数の値を保存しておけば十分である。最後になってから要らないものを捨てれば良い。 そのような考えで、上でRECURSEで実装した漸化式を繰り返しループで実装してみる。あまり創意工夫せず、見え易いようにやってみる。 上の漸化式は、依存項数が3つであるから、値を3つ取っておけば良い。これに入力値を繰り返し回数として加えると4つになるので、上で触れたように、ちょっとスタックアイテム数が多い。そこで、一時退避にリターンスタックを用いることとする。上手く工夫すれば要らないのかも知れないが。 ワード名はseq2としよう。 まず、本体を考える。 初めに、初期値を順に並べて、それに漸化式操作を加え、3つの値が全体として一段階スライドする計算をすればよいわけである。この段階でスタック項目が既に多くなり過ぎるので、リターンスタックを使うが、ともかく、書いてみる。 0 1 2 \ 初期値 -- (n-3) (n-2) (n-1) rot 3 * \ (n-2) (n-1) 3(n-3) R over \ (n-2) (n-1) (n-2) R - 2* \ (n-2) (n-1) 2((n-2)-3(n-3)) over + \ (n-2) (n-1) 2((n-2)-3(n-3))+(n-1)=(n) 以上である。 見ての通り、 Rはデータスタックのトップをリターンスタックに移動して隠す。R は、それをまたデータスタック上に取り出すのである。 2行目からの手続を繰り返し適用すれば、数列はどんどん先にシフトしていく。入力値をむしろ計算繰り返し回数と解釈するわけであるが、3のときに一回処理すれば良いというわけだから、2を引いてループ回数を決めれば良い。この処理の頭に初期値を置くが、forthのループにループ回数を喰わせないといけないので、上で触れたように、ここでもリターンスタックを迂回のために使う。 これらと、計算なしに抜けるための脱出条件に対応する部分を組み合わせると: seq2 ( n -- n ) dup 0 = if drop 0 exit then dup 1 = over 2 = or ?exit 2 - r 0 1 2 r FOR rot 3 * r over r - 2* over + NEXT NIP NIP ; となる。 FOR NEXTはforth標準ではないが、FORがスタックからひとつ値を取って、その回数だけNEXTとの間を繰り返す、簡便なループである。 FORを"0 DO"に、NEXTを"LOOP"に置き換えれば、forth標準で実質同じ内容になる。一番下の行の冒頭で入力値から2を引いてループ回数にし、いったんリターンスタックに隠す。そして、0, 1, 2と初期値をおいた後、リターンスタックから取り出してFOR-NEXTに循環回数として与えるのである。そして、FOR-NEXTに挟まれた、上で述べた数列の前進操作を、必要な回数作用させる。 NIPはforth標準だが、"swap drop"と同値のスタック操作子である。要するに、最後に下の2つの値を落として一番上の必要な項だけ残すのである。 seq2はseq1と比べると劇的に速い。 seq1に40を入力したときは、計算が終わらなくて、待ち切れずiMops強制終了してしまったが、seq2なら50程度でも一瞬である。(ちなみに、40前後でもう4バイト数を越えている。) このアルゴリズムの効率は、明らかにである。 この数列は、適当に作ったわりには挙動が面白く、5個毎に符号を替えながら、次第に振幅を拡大していく。拡大するギザギザグラフである。 手で計算してみたけど、10番目でもう間違えたよ。あー。 ちなみに、同じ発想でフィボナッチ数列のワードも書いてみれば良い。 一応、ひとつの例をfib2として挙げておく: fib2 ( n -- n ) dup 1 if 1- 0 1 rot FOR swap over + NEXT nip then ; これも入力値がある程度大きくても極めて速い。 教訓: 最適化コンパイラによる高速化は、せいぜい数倍、多くは数十パーセント止まりだが、アルゴリズム改良による高速化は、数十倍、ときには100倍以上にもなる。 再帰的処理一般 とはいえ、再帰的処理は漸化式計算に限るわけではない。例えば、Mopsにおいては、多重継承クラスが可能である。そのインスタンスを初期化する際、継承関係のツリー構造を遡って、枝の先(葉)— つまり最上位クラス(むしろ根と考えるのが普通だが) — から順に当クラスの初期化メソッドを実行しなければならないが、そのために再帰的処理を用いている。しかし、そこではワードRECURSEは使っていない。DEFER(MopsではFORWARD)の機構を用いて、互いに呼び出し合う2つのワードによって再帰が実現されている。 このように、あらかじめ構造が確定していない構造木の結節点全てについて処理しようとするような場合には、再帰的処理がもっとも簡単である。そしてこの場合には無駄な処理があるわけではない。再帰処理そのものが「おバカ」なのではない。最適な使用場面もあるのである。「一つ覚え」的な使い方が「おバカ」を招く、と。 iMopsでの多重継承クラスインスタンスの初期化のアルゴリズムについて、ひとつの例として簡単に説明しておこう。継承ツリーの根元から始める。 word1 分枝のリストをチェック、空ならば脱出する リストから取り出された枝データにword2を適用 適用後の枝を切り落とし、1に戻る word2 渡された枝をひとつ遡り、word1を適用 現在の位置の処理(初期化メソッド)を適用 以上である(実際は、インスタンス変数の初期化があるので、もう少し込み入っているが)。 RECURSEを用いた上の計算と考え合わせると、再帰(Recursion)はツリー構造と密接に関わるものであることがわかる。ツリー構造の総当たり手続、といった感じである。もっとも、それもループでできないことはない。しかしそうすると、上で初期化メソッド適用後に前の分岐点に退却するためのデータを保存しておく必要がある。実行速度やコードの書きやすさ、などの比較で決めれば良い。上の例の場合は、初めはループで書いたが、再帰の方がコードが簡単になった。 ここでも、再帰をループに書き換えるポイントは"記憶"である!けれども、ツリー探索の場合、再帰による"自動的記録"が役に立っている。 次 XT(エグゼキューション・トークン) Forth言語概説
https://w.atwiki.jp/ajisaibox/pages/38.html
三間坂兄弟 兄のシエトが、事故で失った妹をよみがえらせようとつくりあげたものがヒューマノイド。 Blue-Gene Projectにおけるシエトは鏡屋研究所の創始者であり管理人。ネムはシエトの死んだ妹、三間坂ネムを模して作られたヒューマノイド。 シエト現在も研究所の管理人であるが本人は既に死亡していて、Terrestrialにおける三間坂シエトは彼の死後ネムによって作られたヒューマノイドである。 つまり、三間坂兄弟は原始のヒューマノイドにして、自己進化を繰り返す最強の個体である。